import { ListNode } from "../数组/对链表进行插入排序"

class Node {
    val: number
    next: Node | null
    random: Node | null
    constructor(val?: number, next?: Node, random?: Node) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
        this.random = (random === undefined ? null : random)
    }
}
/**
 * https://leetcode-cn.com/problems/copy-list-with-random-pointer/
 * 复制带随机指针的链表
 * @param head 
 */
const copyRandomList = (head: Node | null): Node | null => {
    // 空的链表
    if (head === null) return null

    // 旧的node和新的对应
    const map = new Map<Node, Node>();

    // 虚拟头节点
    const dummyHead = new Node(0);

    // 从头开始遍历
    let curr: Node | null = head,
        newHead = dummyHead;

    while (curr !== null) {
        let n: Node;
        if (map.get(curr)) {
            n = map.get(curr)!;
        } else {
            n = new Node(curr.val)
            // 和旧的节点对应起来
            map.set(curr, n)
        }


        // 处理random
        const random = curr.random;
        if (random !== null) {
            // 如果原来已经创建了
            if (map.get(random)) {
                n.random = map.get(random)!
            } else {
                // 原来没有, 创建新的节点
                const newNode = new Node(random.val);

                // 存入map中
                map.set(random, newNode);

                // 给random赋值
                n.random = newNode;
            }
        } else {
            // random为空
            n.random = null
        }

        // 复制给newHead的next并且下一个
        newHead = newHead.next = n;

        // 继续下一个
        curr = curr.next;
    }

    return dummyHead.next;
};

export { }